package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _007_剑指OfferII数组中和为0的三个数 {

    public static void main(String[] args) {


        _007_剑指OfferII数组中和为0的三个数 v = new _007_剑指OfferII数组中和为0的三个数();

        int[] ins = {-1, 0, 1, 2, -1, 4};
        System.out.println(v.threeSum(ins));

    }

    // 固定一个数，然后寻找两数之和等于剩下的数
    public List<List<Integer>> threeSum(int[] nums) {
        // 对数组元素进行排序
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        List<List<Integer>> results = new ArrayList<>();
        int len = nums.length;
        int end = len - 2;
        for (int i = 0; i < end; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int first = nums[i];
            // 寻找两数之和等于-num[i]
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int remain = first + nums[left] + nums[right];
                if (remain > 0) {
                    // 去除重复元素
                    right--;
                } else if (remain < 0) {
                    left++;
                } else {
                    results.add(Arrays.asList(first, nums[left], nums[right]));
                    while (left < right && nums[right] == nums[--right]);
                    while (left < right && nums[left] == nums[++left]);
                }
            }
        }
        return results;
    }

}
